1. Field of the Invention
The present invention relates to a method for ensuring that packets received in a communication system are valid, and if not, to locate and correct them to the extent possible.
2. Description of Related Art
U.S. patent application Ser. No. 08/785,443, now U.S. Pat. No. 6,012,159, which is incorporated herein by reference, discloses a method for reliably transferring packets of data between a transmitter host computer and one or more receiver subscriber computers in a communication system. In particular, that patent application provides various packet-level error correction coding techniques to ensure that large, multimedia data files, including digitized music, still images or moving images, such as may be transmitted using one-way satellite broadcasting, are received error-free despite the effects of various types of noise interfering with the transmitted signal.
In many communication systems, including the aforementioned satellite broadcast system, the data bits or symbols (such as bytes) to be transmitted are most likely to be organized into larger groups called packets. When a file is sent, header packets preceding the information packets are sent. Those header packets contain the address and control information to ensure that the following packets are received by the addressed subscriber computers. Moreover, each packet itself includes header bytes that indicate, inter alia, to which file the packet belongs and the position of the packet within that file. The remaining bytes of the packet are the body which includes the informational data, such as compressed video data. For example, a packet may be 4,096 bytes long, wherein the header portion is the first 16 bytes, and the body portion is the remaining 4,080 bytes. A large digital object is thus transmitted as a sequence of xe2x80x9coriginalxe2x80x9d packets.
In the techniques described in U.S. patent application Ser. No. 08/785,443, now U.S. Pat. No. 6,012,159, an extra number of xe2x80x9cwildcardxe2x80x9d error correcting packets are encoded and transmitted with the original packets to provide a predetermined level of protection against packet loss. For example, if a file contains 180 original packets, an extra 20 wildcard packets may be encoded and transmitted with those 180 original packets, as shown in FIG. 1A, to provide against a loss of 20 original packets (approximately an 11% loss). For the reasons described in that patent application, the addressed subscriber computers can successfully reconstruct the large digital object from the received packets so long as any 180 packets, of the 200 packets transmitted, are successfully received.
Additionally, as also described in U.S. patent application Ser. No. 08/785,443, now U.S. Pat. No. 6,012,159, a large file may be broken into smaller xe2x80x9cchunksxe2x80x9d or xe2x80x9csharesxe2x80x9d, each of which generally contains the same number of packets, to allow the large file to be transmitted and received by the system. Each share is individually encoded, transmitted, received and reconstructed (decoded). The file is made whole from the individual reconstructed shares. As also discussed therein, the packets of the shares may also be interleaved to provide additional protection against noise. For example, a data file of 360 original packets and 40 wildcard packets may be divided into two shares of 200 interleaved packets each, as shown in FIG. 1B. Of course, as the files become larger, the number of shares will increase.
As disclosed in U.S. patent application Ser. No. 08/785,443, now U.S. Pat. No. 6,012,159 packet-level error detection processing in the receiving subscriber computers provides an indication that a received packet is xe2x80x9cgoodxe2x80x9d or xe2x80x9cbadxe2x80x9d. Also, an indication is made if a packet has not been received at all, i.e., xe2x80x9clostxe2x80x9d. The bad packets are marked as lost and are not used in further decoding. As further explained therein, as long as the number or lost packets does not exceed the number of wildcard packets, the original packets of the file or share may be completely and correctly reconstructed. Continuing the above examples, for each file or share, at least 180 packets of the 200 transmitted packets must be received as xe2x80x9cgoodxe2x80x9d packets to allow the reconstruction of the original 180 packets. The techniques for decoding the received xe2x80x9cgoodxe2x80x9d packets to reconstruct the original packets are described more fully in the above-identified application.
Those techniques assumes that the underlying packet-level error detection processing does not make any errors, i.e., that when a packet is marked as xe2x80x9cgoodxe2x80x9d, it is truly error-free. However, this is not always the case. Occasionally, a packet is marked as xe2x80x9cgoodxe2x80x9d when it actually has one or more bit or symbol errors. This may occur if the error detection scheme of the underlying subscriber computer is not robust. For example, the subscriber computer may use a simple checksum error detection scheme to determine whether or not the packet is good. If the checksum fails, then the packet is marked as xe2x80x9cbadxe2x80x9d. But even if the checksum passes and the packet is marked xe2x80x9cgoodxe2x80x9d, there is a certain non-trivial probability that the packet is actually bad. In this case, the reconstructed original packets will be erroneous because the reconstruction process used a bad packet, mistakenly marked as xe2x80x9cgoodxe2x80x9d by the packet-level error detection processing. Accordingly, the subscriber computer may use an additional level of packet error detection, such as a length check on a word in a header, to reduce the number of these erroneously-marked packets. Thus, it is unlikely that more than one packet in a share will be erroneously marked. In any event, the extremely robust and strong packet reconstruction techniques described in the above-identified patent application may be weakened by a poor packet-level error detection scheme in the underlying subscriber computer.
Accordingly, it would be desirable to provide a method and system that overcomes the above-described problems. In particular, a method is provided that verifies whether the original packets have been correctly reconstructed, and if not, locates an erroneously marked packet so that it may be removed from the reconstruction process. The reconstruction, verification and location process may then be repeated, if there are enough remaining packets, until the reconstructed original packets are deemed correct.
Because the method of the present invention detects and locates erroneous packets independently of the packet-level error detection processing of the subscriber computer, successful packet reconstruction is not hampered by the inability of the subscriber computer to detect erroneous packets reliably.